import java.util.*;

/**
 * 94. 二叉树的中序遍历
 * https://leetcode-cn.com/problems/binary-tree-inorder-traversal/
 */
public class Solutions_94 {
    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        root.right = new TreeNode(2);
        root.right.left = new TreeNode(3);  // output: {1, 3, 2}

        List<Integer> result = inorderTraversal2(root);
        System.out.println(result);
    }

    // 迭代
    public static List<Integer> inorderTraversal2(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        if (root == null) {
            return res;
        }
        // 创建辅助栈来完成二叉树的迭代
        Deque<TreeNode> stack = new LinkedList<>();
        TreeNode cur = root;
        // 判断条件：栈不为空，cur 不为空
        while (!stack.isEmpty() || cur != null) {
            // 父节点的左子节点依次入栈
            while (cur != null) {
                stack.push(cur);
                cur = cur.left;
            }
            // 取出栈中元素
            TreeNode temp = stack.pop();
            res.add(temp.val);
            cur = temp.right;
        }
        return res;
    }

    // 递归
    public static List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        inorderTraversal_dfs(root, res);
        return res;
    }

    public static void inorderTraversal_dfs(TreeNode root, List<Integer> res) {
        if (root == null) {
            return;
        }
        // 左
        inorderTraversal_dfs(root.left, res);
        // 中
        res.add(root.val);
        // 右
        inorderTraversal_dfs(root.right, res);
    }
}
